Orientations, lattice polytopes, and group arrangements III: Cartesian product arrangements and applications to the Tutte type polynomials of graphs

摘要

A common generalization for the chromatic polynomial and the flow polynomialof a graph $G$ is the Tutte polynomial $T(G;x,y)$. The combinatorial meaningfor the coefficients of $T$ was discovered by Tutte at the beginning of itsdefinition. However, for a long time the combinatorial meaning for the valuesof $T$ is missing, except for a few values such as $T(G;i,j)$, where $1\leqi,j\leq 2$, until recently for $T(G;1,0)$ and $T(G;0,1)$. In this third one ofa series of papers, we introduce product valuations, cartesian productarrangements, and multivariable characteristic polynomials, and apply thetheory of product arrangement to the tension-flow group associated with graphs.Three types of tension-flows are studied in details: elliptic, parabolic, andhyperbolic; each type produces a two-variable polynomial for graphs. Weightedpolynomials are introduced and their reciprocity laws are obtained. The dualversions for the parabolic case turns out to include Whitney's rank generatingpolynomial and the Tutte polynomial as special cases. The product arrangementpart is of interest for its own right. The application part to graphs can bemodified to matroids.